package com.jeff.practice;

import java.util.ArrayList;
import java.util.Arrays;

/**获取滑动窗口最大值
 * 思路:
 * 1. 定义一个数组kArr，长度为k，用来存放滑动窗口的元素
 * 2. 初始化kArr，将arr的前k个元素存入kArr
 * 3. 对kArr进行排序，得到窗口最大值
 * 4. 遍历arr，从第k个元素开始，每次将滑动窗口右移一个元素，并更新窗口最大值
 * 5. 保存窗口最大值到list中
 * 6. 返回list
 * @author yaojianfeng
 */
public class FindSlideWindowMaxValue {
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, -4, 5, 3, 6, 7};
        ArrayList<Integer> maxSlideWindow = findMaxSlideWindow(arr, 3);
        System.out.println(maxSlideWindow);
    }


    public static ArrayList<Integer> findMaxSlideWindow(int[] arr, int k) {

        int[] kArr = new int[k];
        //初始化滑动窗口
        System.arraycopy(arr, 0, kArr, 0, k);
        //求窗口最大值
        Arrays.sort(kArr);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(kArr[k - 1]);
        for (int i = k; i < arr.length; i++) {
            //滑动窗口右移
            System.arraycopy(arr, i - k + 1, kArr, 0, k);
            //更新窗口最大值
            Arrays.sort(kArr);
            list.add(kArr[k - 1]);
        }
        return list;
    }
}
